#ifndef SORT_H_
#define SORT_H_

#include <algorithm>
#include <cstddef>
#include <type_traits>
#include <vector>

namespace lxj
{

constexpr size_t BASE = 10;
// 返回number在BASE进制下有几位
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline constexpr size_t bits(T number)
{
    size_t ans = 0;
    while (number > 0) {
        number /= BASE;
        ans++;
    }
    return ans;
}

// 基数排序核心代码
// 数据必须为非负整数
// bits是元素中最大值在BASE进制下有几位
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline void r_sort(T* arr, size_t size, size_t bits)
{
    std::vector<T> help(size);
    size_t         cnt[BASE] = {};
    for (size_t offst = 1; bits > 0; offst *= BASE, bits--) {
        for (auto& i : cnt) {
            i = 0;
        }
        for (auto p = arr; p != arr + size; p++) {
            cnt[(*p / offst) % BASE]++;
        }
        for (int i = 1; i < BASE; i++) {
            cnt[i] = cnt[i] + cnt[i - 1];
        }

        for (int i = size - 1; i >= 0; i--) {
            const size_t index = --cnt[(*(arr + i) / offst) % BASE];
            help[index]        = *(arr + i);
        }
        for (T *p1 = arr, *p2 = help.data(); p1 != arr + size; p1++, p2++) {
            *p1 = *p2;
        }
    }
}

// 基数排序对数据有要求
// 必须为整数
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline void radix_sort(T* arr, size_t size)
{
    if (size == 0) return;
    T min = *std::min_element(arr, arr + size);
    for (T* p = arr; p != arr + size; p++) {
        *p -= min;
    }
    T max = *std::max_element(arr, arr + size);
    r_sort(arr, size, bits(max));
    for (T* p = arr; p != arr + size; p++) {
        *p += min;
    }
}
}   // namespace lxj

#endif